#define DEBUG
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn=42;

int max(int a, int b) {
  return a>b ? a : b;
}

class Graph {
public:
  int n, m, ind[maxn+1], to[maxn*maxn+1], val[maxn*maxn+1], link[maxn*maxn+1], a[maxn+1], b[maxn+1], mapa[maxn+1], mapb[maxn+1], cont;

  void addSide(int u, int v, int t) {
    m++;
    to[m] = v;
    val[m] = t;
    link[m] = ind[u];
    ind[u] = m;
  }

  void initA() {
    for (int i=ind[1]; i; i=link[i]) {
      a[++a[0]] = to[i];
      mapa[to[i]] = a[0];
      cont += !val[i];
    }
  }

  void initB() {
    static bool book[maxn+1];
    book[1] = true;
    for (int i=1; i<=a[0]; i++) {
      book[a[i]] = true;
    }
    for (int i=1; i<=a[0]; i++) {
      for (int j=ind[a[i]]; j; j=link[j]) {
	if (!book[to[j]]) {
	  book[to[j]] = true;
	  b[++b[0]] = to[j];
	  mapb[to[j]] = b[0];
	}
      }
    }
  }
};

int solveA(Graph *g) {
  static int f[1<<20];

  for (int i=0; i<(1<<g->a[0]); i++) {
    // if (f[i] || !i) {
      static bool book[maxn+1];
      memset(book, 0, sizeof(book));
      for (int j=g->ind[1]; j; j=g->link[j]) {
	int x=g->to[j];
	if ((i>>(g->mapa[x]-1))&1) {
	  for (int k=g->ind[x]; k; k=g->link[k]) {
	    if (g->to[k]!=1) {
	      book[g->to[k]] = true;
	    }
	  }
	}
      }
      for (int j=g->ind[1]; j; j=g->link[j]) {
	int x=g->to[j], y=g->val[j], cont=0;
	if (!((i>>(g->mapa[x]-1))&1)) {
	  for (int k=g->ind[x]; k; k=g->link[k]) {
	    if (g->mapb[g->to[k]] && !book[g->to[k]]) {
	      cont += !(y^(g->val[k]));
	    }
	  }
	  f[i|(1<<(g->mapa[x]-1))] = max(f[i|(1<<(g->mapa[x]-1))], f[i]+cont);
	}
      }
    // }
  }
  return f[(1<<g->a[0])-1];
}

int solveB(Graph *g) {
  static int f[1<<20];
  
  for (int i=0; i<(1<<g->b[0]); i++) {
    if (f[i] || !i) {
      for (int j=g->ind[1]; j; j=g->link[j]) {
	int x=g->to[j], y=g->val[j], cont=0, s=0;
	for (int k=g->ind[x]; k; k=g->link[k]) {
	  int u=g->to[k], v=g->val[k];
	  if (g->mapb[u]) {
	    if (!((i>>(g->mapb[u]-1))&1)) {
	      s = s|(1<<(g->mapb[u]-1));
	      cont += !(y^v);
	    }
	  }
	}
	if (s) {
	  f[i|s] = max(f[i|s], f[i]+cont);
	}
      }
    }
  }

  return f[(1<<g->b[0])-1];
}

int main() {
  freopen("friends.in", "r", stdin);
  freopen("friends.out", "w", stdout);

  static Graph g;
  int n, m;
  scanf("%d %d", &n, &m);
  g.n = n;
  for (int i=1; i<=m; i++) {
    int u, v, t;
    scanf("%d %d %d", &u, &v, &t);
    g.addSide(u, v, t);
    g.addSide(v, u, t);
  }

  g.initA();
  g.initB();

  printf("%d", (g.a[0]<g.b[0] ? solveA(&g) : solveB(&g))+g.cont);

  fclose(stdin);
  fclose(stdout);
  return 0;
}
